package MySearch;


import MyBinaryTree.BiTree;
import MySort.RecordNode;

public class myFind {
    // 查找算法

    public RecordNode[] list;//待排序顺序表的记录集合
    public int len;//顺序表的长度
    public int maxSize;//顺序表的最大存储空间
    public myFind(int maxSize){
        list=new RecordNode[maxSize];
        len=0;
        this.maxSize=maxSize;
    }

    /**
     * 顺序查找
     * @param key 待查找值
     * @return 返回的该值的数组下标 否则返回-1
     */
    public int seqSearch(int key){
        for(int i=0; i<len; i++){
            if(list[i].key == key){
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分法查找
     * @param key 待查找值
     * @return 该值位于的数组下标
     */
    public int binarySearch(int key){
        if(len > 0){
            // 上下坐标
            int low = 0;
            int high = len-1;
            // 当 high=low-1 时最后还需要移动一次才能够满足 情况为 (low+high) = 2low = 2high
            // 此时mid才能被找到所以这里边界判断位low<= high
            while(low <= high){
                int mid = (low+high)/2;
                if(list[mid].key == key){
                    return mid;
                }else if(list[mid].key > key){
                    // 由于上面已经判断是否相同了，不同说明这个位置不对，且大于目标所以指针移动到mid的左侧
                    high = mid+1;
                }else if(list[mid].key < key){
                    // 由于上面已经判断是否相同了，不同说明这个位置不对，且小于目标所以指针移动到mid的右侧
                    low = mid+1;
                }
            }
        }
        return -1;
    }




}
